#include <jni.h>
#include <string>
#include <android/log.h>
#include <queue>
#include <cmath>
#include <stdlib.h>
#include <PriorityQueue.hpp>

using namespace std;
template<class T>
class TreeNode {
public:
    // 构造函数
    TreeNode(T data) {
        this->data = data;
    }
    T data; // 数据(A,B,C...), 数据域
    TreeNode *left = NULL;  // 左子树
    TreeNode *right = NULL; // 右子树
};

// 二叉树的序列化，使用递归实现。
void serializeTree( TreeNode<char> *pNode, string* str) {
    if(pNode == NULL) {
        str->append("#"); // 无根节点(左、右)，输出#号。
        return;
    }
    // 1. 首先输出根节点（自己）
    // *str += pNode->data;
    str->append(string(1, pNode->data)); // 添加1个字母，如 A
    // 2. 遍历左节点
    serializeTree(pNode->left, str);
    // 3. 遍历右节点
    serializeTree(pNode->right, str);
}

// 反序列化 二叉树。 str= "ABD##E##C#F##"
// 二级指针的好处：新的变量，但是还是指向原来的区域。
TreeNode<char>* deserializeTree(char **str) { // 传递二级指针
    if(**str == '#') {
        *str += 1; // 获取下一个
        return NULL;
    }

    TreeNode<char> *node =  new TreeNode<char>(**str) // 构建树
    *str += 1; // 获取下一个
    node.left = deserializeTree(str); // 解析左边
    node.right = deserializeTree(str); // 解析右边
    return node;
}

// 堆的调整：不断地调整大根堆 ，k是索引，n就是length长度。
void adjustHeap(int arr[], int k, int n) {
    // 从0开始的，所以要+1
    while(k *2 +1 <= n) { // 到底部了。判断是否有左孩子，没有左孩子 肯定也就没有右孩子。
        // 最大指向左孩子 2*k +1； 右边是2*k +2
        int max = 2*k +1;
        // 判断是否有 右孩子. 有有孩子，且右孩子大于左孩子。
        if(max +1 <= n && arr[max+1] > arr[max]) {
            max = max+1; // 2*k +2
        }
        // 最大的还是自己，跳出去；否则就交换。
        if(arr[k] > arr[max]) {
            break;
        }
        // 交换：最大的往上冒。 arr[k] <= arr[max] 时，交换值。让堆为大堆。
        swap(arr[k], arr[max]);
        // 继续往下走
        k = max;
    }
}

// 堆排序， 按照从小到大排序。
void headSort(int arr[], int len) {
    // 1. 从最后一个非 叶子节点的节点【i= len/2 -1】，开始调整为 大根堆。
    for(int i= len/2 -1; i>=0; --i) {
        adjustHeap(arr, i, len); // 调整为大根堆。
    }
    // 2.第一个与最后一个交换，然后再调整为 大根堆。但是不考虑最后一个(i==0)item。
    // i>0 最后一个不要处理(最后一个已经是最大的，优点类似冒泡排序)
    for(int i =len-1; i>0 ; i--) { // 从后往前，交换值，重新堆排序。
        // 第一个与最后一个交换【让最大的，排列在最后面】，依次循环，最终达到从小到大排序的效果。
        swap(arr[0], arr[i]);
        // 再次调整为大根堆，
        adjustHeap(arr, 0, i); // 对第0个位置进行调整，最后一个item不考虑。
    }
}



extern "C"
JNIEXPORT jstring
JNICALL
Java_com_ndk_day42_MainActivity_stringFromJNI(
        JNIEnv *env,
        jobject /* this */) {

    // 新建节点，放入内存中。
    TreeNode<char> *A = new TreeNode<char>('A');
    TreeNode<char> *B = new TreeNode<char>('B');
    TreeNode<char> *C = new TreeNode<char>('C');
    TreeNode<char> *D = new TreeNode<char>('D');
    TreeNode<char> *E = new TreeNode<char>('E');
    TreeNode<char> *F = new TreeNode<char>('F');
    TreeNode<char> *G = new TreeNode<char>('G');

    A->left = B; // 设置A的左右子节点。
    A->right = C;

    B->left = D; // 设置B的左右子节点
    B->right = E;
    C->right = F; // 设置C的右子节点。

    // 序列化
  //    string str;
  //    serializeTree(A, &str); // 传递地址
  //    __android_log_print(ANDROID_LOG_ERROR, "TAG", "serialize = %s", str.c_str()); // ABD##E##C#F##

    // 反序列化
 //   char* treeStr = "ABD##E##C#F##"; // 一级指针，可以看成数组。解析一个后，指针要往后挪动
 //   TreeNode<char> *node = deserializeTree(&treeStr); // 传递二级指针
 //   string str;
 //   serializeTree(node, &str); // 序列化输出
 //   __android_log_print(ANDROID_LOG_ERROR, "TAG", "serialize = %s", str.c_str());

/*    int n = 10;
    PriorityQueue<int> pQueue(n); // 构建queue
    for(int i=0; i<n; i++) {
        pQueue.push(rand() % 100); // 100 内的随机数
    }
    while(!pQueue.isEmpty()) {
        // 不断弹出来
         __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", pQueue.pop());
    } */

    PriorityQueue<int> pQueue(n);
    int n=4;
    int arr[] = {-4,-5, 7,8};
   /*  // *拷贝排序*。
   for(int i=0; i<n; i++) {
        pQueue.push(arr[i]); // 拷贝到队列中
    }
    for(int i=0; i<n; i++) {
       arr[i] =  pQueue.pop(); // 从队列拷贝到数组中
    } */
    // 原地排序

    // 原地排序，数组 化成堆来排序。(-4,-5,7,8)--> (-5,-4,7,8)
    headSort(arr, n);
    // 输出排好顺序的数组。想要从小到大排序，可以数组arr 反过来输出。
    for(int i=0; i<n; i++) {
         __android_log_print(ANDROID_LOG_ERROR, "TAG", "%d", arr[i]);
    }


    std::string hello = "Hello from C++";
    return env->NewStringUTF(hello.c_str());
}


